
/*
https://leetcode.cn/problems/maximum-score-after-applying-operations-on-a-tree/description/
*/

----------------------------------------------------------------------------------------------------------------------------------------------------------------


#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     * 计算在树上执行一系列操作后可以获得的最大得分。
     *
     * @param Edges 树的边列表
     * @param Val 每个节点的初始值
     * @return 最大得分
     */
    long long MaximumScoreAfterOperations(vector<vector<int>>& Edges, vector<int>& Val) {
        int N = Val.size();
        vector<vector<int>> G(N); // 邻接表表示的图结构

        // 构建图结构
        for (const auto &Edge : Edges) {
            G[Edge[0]].push_back(Edge[1]);
            G[Edge[1]].push_back(Edge[0]);
        }

        long long Memo[N][2]; // 记忆化数组，存储已计算的结果
        memset(Memo, -1, sizeof(Memo));

        // 定义递归函数，进行深度优先搜索
        function<long long(int, bool, int)> Dfs = [&](int I, bool Choice, int Fa) -> long long {
            // 如果是叶子节点，直接返回根据Choice决定的值
            if (G[I].size() == 1 && G[I][0] == Fa) {
                return Choice ? Val[I] : 0;
            }

            long long &Ans = Memo[I][Choice];
            if (Ans != -1) return Ans; // 如果已经计算过，直接返回结果--------

            if (Choice) {
                Ans = Val[I]; // 如果选择了当前节点，则加上其值
                for (auto V : G[I]) {
                    if (V == Fa) continue; // 跳过父节点------
                    Ans += Dfs(V, true, I); // 子节点也必须被选择------
            } else {
                long long Res1 = Val[I], Res2 = 0;
                for (auto V : G[I]) {
                    if (V == Fa) continue; // 跳过父节点
                    Res1 += Dfs(V, false, I); // 子节点不被选择的情况
                    Res2 += Dfs(V, true, I); // 子节点被选择的情况
                }
                Ans = max(Res1, Res2); // 取两种情况中的最大值
            }
            return Ans;
        };

        // 从根节点开始，不选择根节点------
        return Dfs(0, false, -1);
    }
};


------------------------------------------------------------------------------------------------------------------------------------------------------